package Algorithm.StackAndQueue;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author cj
 * @Date 2021/11/11 19:56
 */
public class getNum {

    public static int getNum1(int[] arr, int num) {
        Deque<Integer> qmax = new LinkedList<>();
        Deque<Integer> qmin = new LinkedList<>();
        int res = 0;
        int j = 0;
        for (int i = 0; i < arr.length; i++) {
            if (qmin.isEmpty() || qmin.getLast() != j) {
                while (!qmin.isEmpty() && arr[qmin.getLast()] >= arr[j]) {
                    qmin.removeLast();
                }
                qmin.addLast(j);
                while (!qmax.isEmpty() && arr[qmax.getLast()] <= arr[j]) {
                    qmax.removeLast();
                }
                qmax.addLast(j);
                if (arr[qmax.getFirst()] - arr[qmin.getFirst()] > num) {
                    break;
                }
                j++;
            }
            res += j - i;
            if (qmax.getFirst() == i) {
                qmax.removeFirst();
            }
            if (qmin.getFirst() == i) {
                qmin.removeFirst();
            }
        }
        return res;
    }
}
